package com.yanceysong.codetop.s21_s30;

import com.yanceysong.common.ListNode;


public class S21_Mid_92_反转链表_II {
    /**
     * LeetCode链接
     * <a href="https://leetcode.cn/problems/reverse-linked-list-ii/description/">...</a>
     * <p>
     * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
     * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
     * <p>
     * 示例1：
     * 输入：head = [1,2,3,4,5], left = 2, right = 4
     * 输出：[1,4,3,2,5]
     * <p>
     * 示例2：
     * 输入：head = [5], left = 1, right = 1
     * 输出：[5]
     * <p>
     * 提示：
     * 链表中节点数目为 n
     * 1 <= n <= 500
     * -500 <= Node.val <= 500
     * 1 <= left <= right <= n
     * <p>
     * 解题：
     * {@link S21_Mid_92_反转链表_II#reverseBetween(ListNode, int, int)}
     * <p>
     * ==================== 反转链表II算法图解 ====================
     * <p>
     * 算法思路：穿针引线法 (迭代)
     * 1. 使用虚拟头节点 `dummy` 简化边界处理（特别是 `left=1` 的情况）。
     * 2. 找到反转区间的 **前驱节点** `preLeft`。
     * 3. 从 `preLeft` 开始，使用 **头插法** 逐个将反转区间的节点移动到 `preLeft` 之后。
     * <p>
     * 执行示例：head = [1,2,3,4,5], left = 2, right = 4
     * <p>
     * 初始状态：
     * dummy -> 1 -> 2 -> 3 -> 4 -> 5
     *          |    |
     *       preLeft curr (leftNode)
     * <p>
     * 迭代过程 (反转 right - left 次):
     * <p>
     * 第1次迭代 (移动节点3):
     * 1. `next = curr.next` (next = 3)
     * 2. `curr.next = next.next` (2 -> 4)
     * 3. `next.next = preLeft.next` (3 -> 2)
     * 4. `preLeft.next = next` (1 -> 3)
     * <p>
     * 链表状态:
     * dummy -> 1 -> 3 -> 2 -> 4 -> 5
     *          |         |
     *       preLeft    curr
     * <p>
     * 第2次迭代 (移动节点4):
     * 1. `next = curr.next` (next = 4)
     * 2. `curr.next = next.next` (2 -> 5)
     * 3. `next.next = preLeft.next` (4 -> 3)
     * 4. `preLeft.next = next` (1 -> 4)
     * <p>
     * 链表状态:
     * dummy -> 1 -> 4 -> 3 -> 2 -> 5
     *          |              |
     *       preLeft         curr
     * <p>
     * 最终结果：1 -> 4 -> 3 -> 2 -> 5
     * <p>
     * ==================== 算法复杂度分析 ====================
     * <p>
     * 时间复杂度：O(n)，需要遍历链表找到 left 和 right 的位置。
     * 空间复杂度：O(1)，只使用了常数个额外指针。
     * <p>
     * ===============================================================
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 边界检查：空链表或无需反转
        if (head == null || left == right) {
            return head;
        }

        // 使用虚拟头节点简化 left = 1 的情况
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // 步骤1：找到反转区间的前驱节点 preLeft
        ListNode preLeft = dummy;
        for (int i = 1; i < left; i++) {
            preLeft = preLeft.next;
        }

        // 步骤2：初始化当前节点 curr，准备开始反转
        ListNode curr = preLeft.next; // curr 指向反转区间的第一个节点

        // 步骤3：使用“穿针引线法”进行头插反转
        // 循环 right - left 次，将 curr 后面的节点逐个移动到 preLeft 后面
        for (int i = 0; i < right - left; i++) {
            // 1. 记录待移动的节点
            ListNode nextNode = curr.next;

            // 2. 将 curr 连接到 nextNode 的下一个节点 (断开 nextNode)
            curr.next = nextNode.next;

            // 3. 将 nextNode 插入到 preLeft 后面 (头插)
            nextNode.next = preLeft.next;
            preLeft.next = nextNode;
        }

        // 返回虚拟头节点的下一个节点
        return dummy.next;
    }

    public static void main(String[] args) {
        S21_Mid_92_反转链表_II solution = new S21_Mid_92_反转链表_II();

        System.out.println("=== 反转链表II测试开始 ===");

        // 测试1: 基本功能测试 - 题目示例
        System.out.println("\n--- 测试1: 基本功能测试 (题目示例) ---");
        testBasicExamples(solution);

        // 测试2: 边界情况测试
        System.out.println("\n--- 测试2: 边界情况测试 ---");
        testBoundaryCases(solution);

        // 测试3: 不同反转区间测试
        System.out.println("\n--- 测试3: 不同反转区间测试 ---");
        testDifferentRanges(solution);

        // 测试4: 特殊情况测试
        System.out.println("\n--- 测试4: 特殊情况测试 ---");
        testSpecialCases(solution);

        // 测试5: 性能测试
        System.out.println("\n--- 测试5: 性能测试 ---");
        testPerformance(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 测试基本功能 - 题目给出的示例
     */
    private static void testBasicExamples(S21_Mid_92_反转链表_II solution) {
        // 示例1: [1,2,3,4,5], left=2, right=4 -> [1,4,3,2,5]
        int[] input1 = {1, 2, 3, 4, 5};
        int[] expected1 = {1, 4, 3, 2, 5};
        testReverseBetween(solution, input1, 2, 4, expected1, "题目示例1");

        // 示例2: [5], left=1, right=1 -> [5]
        int[] input2 = {5};
        int[] expected2 = {5};
        testReverseBetween(solution, input2, 1, 1, expected2, "题目示例2(单节点)");

        System.out.println("✓ 基本功能测试通过");
    }

    /**
     * 测试边界情况
     */
    private static void testBoundaryCases(S21_Mid_92_反转链表_II solution) {
        // 测试1: null输入
        ListNode result1 = solution.reverseBetween(null, 1, 1);
        System.out.println("null输入: null -> " + (result1 == null ? "null" : "非null") + " (期望: null)");
        assert result1 == null : "null输入测试失败";

        // 测试2: 反转整个链表
        int[] input2 = {1, 2, 3, 4, 5};
        int[] expected2 = {5, 4, 3, 2, 1};
        testReverseBetween(solution, input2, 1, 5, expected2, "反转整个链表");

        // 测试3: 从头开始反转
        int[] input3 = {1, 2, 3, 4, 5};
        int[] expected3 = {3, 2, 1, 4, 5};
        testReverseBetween(solution, input3, 1, 3, expected3, "从头开始反转");

        // 测试4: 反转到结尾
        int[] input4 = {1, 2, 3, 4, 5};
        int[] expected4 = {1, 2, 5, 4, 3};
        testReverseBetween(solution, input4, 3, 5, expected4, "反转到结尾");

        // 测试5: left = right
        int[] input5 = {1, 2, 3, 4, 5};
        int[] expected5 = {1, 2, 3, 4, 5};
        testReverseBetween(solution, input5, 3, 3, expected5, "left = right");

        System.out.println("✓ 边界情况测试通过");
    }

    /**
     * 测试不同反转区间
     */
    private static void testDifferentRanges(S21_Mid_92_反转链表_II solution) {
        int[] input = {10, 20, 30, 40, 50, 60, 70};

        // 测试1: 中间部分
        int[] expected1 = {10, 20, 50, 40, 30, 60, 70};
        testReverseBetween(solution, input, 3, 5, expected1, "反转中间部分");

        // 测试2: 两个节点
        int[] expected2 = {10, 30, 20, 40, 50, 60, 70};
        testReverseBetween(solution, new int[]{10, 20, 30, 40, 50, 60, 70}, 2, 3, expected2, "反转两个节点");

        // 测试3: 较长区间
        int[] expected3 = {10, 60, 50, 40, 30, 20, 70};
        testReverseBetween(solution, input, 2, 6, expected3, "反转较长区间");

        System.out.println("✓ 不同反转区间测试通过");
    }

    /**
     * 测试特殊情况
     */
    private static void testSpecialCases(S21_Mid_92_反转链表_II solution) {
        // 测试1: 包含负数
        int[] input1 = {-1, -2, 3, 4, -5};
        int[] expected1 = {-1, 4, 3, -2, -5};
        testReverseBetween(solution, input1, 2, 4, expected1, "包含负数");

        // 测试2: 包含零
        int[] input2 = {1, 0, 2, 0, 3};
        int[] expected2 = {1, 0, 2, 0, 3};
        testReverseBetween(solution, input2, 2, 4, expected2, "包含零");

        // 测试3: 相同元素
        int[] input3 = {1, 2, 2, 2, 3};
        int[] expected3 = {1, 2, 2, 2, 3};
        testReverseBetween(solution, input3, 2, 4, expected3, "反转相同元素");

        System.out.println("✓ 特殊情况测试通过");
    }

    /**
     * 测试性能
     */
    private static void testPerformance(S21_Mid_92_反转链表_II solution) {
        // 测试1: 中等规模
        System.out.println("性能测试1: 100个节点");
        testPerformanceCase(solution, 100, 10, 90);

        // 测试2: 较大规模
        System.out.println("性能测试2: 500个节点");
        testPerformanceCase(solution, 500, 100, 400);

        System.out.println("✓ 性能测试通过");
    }

    /**
     * 辅助方法：性能测试用例
     */
    private static void testPerformanceCase(S21_Mid_92_反转链表_II solution, int nodeCount, int left, int right) {
        ListNode head = createList(createRangeArray(1, nodeCount));
        long startTime = System.currentTimeMillis();
        ListNode result = solution.reverseBetween(head, left, right);
        long endTime = System.currentTimeMillis();

        assert result != null : "性能测试：结果不应为空";
        System.out.println("  节点数: " + nodeCount + ", left=" + left + ", right=" + right +
                           ", 执行时间: " + (endTime - startTime) + "ms");

        assert (endTime - startTime) < 100 : "性能测试：执行时间过长";
    }

    /**
     * 创建链表的辅助方法
     */
    private static ListNode createList(int[] values) {
        if (values == null || values.length == 0) return null;
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        for (int value : values) {
            current.next = new ListNode(value);
            current = current.next;
        }
        return dummy.next;
    }

    /**
     * 将链表转换为数组的辅助方法
     */
    private static int[] listToArray(ListNode head) {
        if (head == null) return new int[0];
        int size = 0;
        ListNode current = head;
        while (current != null) {
            size++;
            current = current.next;
        }
        int[] array = new int[size];
        current = head;
        for (int i = 0; i < size; i++) {
            array[i] = current.val;
            current = current.next;
        }
        return array;
    }

    /**
     * 打印数组的辅助方法
     */
    private static void printArray(int[] arr) {
        System.out.print(java.util.Arrays.toString(arr));
    }

    /**
     * 创建范围数组的辅助方法
     */
    private static int[] createRangeArray(int start, int end) {
        int[] array = new int[end - start + 1];
        for (int i = 0; i < array.length; i++) {
            array[i] = start + i;
        }
        return array;
    }

    /**
     * 测试反转链表的辅助方法
     */
    private static void testReverseBetween(S21_Mid_92_反转链表_II solution, int[] inputArray, int left, int right, int[] expected, String description) {
        ListNode head = createList(inputArray);
        ListNode result = solution.reverseBetween(head, left, right);
        int[] actual = listToArray(result);

        System.out.print(description + " - 输入: ");
        printArray(inputArray);
        System.out.print(", left=" + left + ", right=" + right + " -> 输出: ");
        printArray(actual);
        System.out.print(" (期望: ");
        printArray(expected);
        System.out.println(")");

        assert java.util.Arrays.equals(actual, expected) : description + "测试失败";
    }
}

